Computer-aided design (CAD) is commonly used by chip designers to plan circuit layouts. Through the use of CAD-generated circuit diagrams, chip designers can easily mock-up multiple circuit layouts, anticipate potential problems in a particular layout and determine space-saving configurations.
To be a useful tool in chip design, however, the CAD-generated circuit must be as precise as possible. Specifically, circuit layouts typically involve multiple shapes, many of which intersect with and/or overlap one another. The interaction of the shapes is very important. Any misrepresentation of an intersection or overlap of one shape with another can result in an erroneous point of connectivity in the design, thus producing a faulty circuit.
Several different CAD circuit design systems currently exist. Some of these systems employ a “smart-rounding” technique based on an integer grid. With smart-rounding, whenever a non-integer coordinate is encountered in a design rounding is performed to the next-closest integer coordinate (so as to preserve the connectivity). Smart-rounding, however, requires a lot of extra runtime and extra work on the part of the system operator. Further, whenever rounding is involved, there is no guarantee that connectivity can be preserved in all cases. Others use infinite precision rational coordinates, thus avoiding errors associated with rounding. The use of infinite precision rational coordinates, however, makes memory usage grow very rapidly and results in a runtime that is unacceptably slow.
With very-large-scale integration (VLSI), wherein potentially thousands of circuits are integrated on a single chip, the complexity of the design increases exponentially, as does the margin for error. Further, many VLSI applications, in particular lithography and process simulations, introduce designs that include arbitrary angles. Some conventional CAD systems can accommodate angles in a design, as long as the angles are multiples of 45 degrees. Thus, most arbitrary angles would not qualify. As such, complex VLSI designs are beyond the capabilities of conventional CAD tools.
Therefore, a more accurate and efficient design system that can accommodate complex circuits, such as VLSI, would be desirable.